package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;

/*
 * 
原题　
	There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
	
	The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
	
	Note:
	All costs are positive integers.
	
题目大意
	有一排n个房子，每个房子都可以涂上三种颜色之一：红色，蓝色或绿色。 以某种颜色绘画每个房子的成本是不同的。 你必须画所有的房子，使两个相邻的房子没有相同的颜色。
	
	用某种颜色绘画每个房子的成本由n×3成本矩阵表示。 例如，成本[0] [0]是彩色房子0的颜色为红色的成本; 成本[1] [2]是彩色房屋1的成本，彩色绿色等等...找到绘制所有房屋的最低成本。
	
	注意：
	所有成本都是正整数。
	
解题思路
	这道题说有n个房子，每个房子可以用红绿蓝三种颜色刷，每个房子的用每种颜色刷的花费都不同，限制条件是相邻的房子不能用相同的颜色来刷，现在让我们求刷完所有的房子的最低花费是多少。
		这题跟House Robber II和House Robber很类似，不过那题不是每个房子都抢，相邻的房子不抢，
			而这道题是每个房子都刷，相邻的房子不能刷同一种颜色。
		而Paint Fence那道题主要考察我们有多少种刷法，这几道题很类似，但都不一样，需要我们分别区分。但是它们的解题思想都一样，需要用动态规划Dynamic Programming来做，
			这道题我们需要维护一个二维的动态数组dp，其中dp[i][j]表示刷到第i+1房子用颜色j的最小花费，递推式为:
	
	dp[i][j] = dp[i][j] + min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3])；
	
	这个也比较好理解，如果当前的房子要用红色刷，那么上一个房子只能用绿色或蓝色来刷，
		那么我们要求刷到当前房子，且当前房子用红色刷的最小花费就等于当前房子用红色刷的钱加上刷到上一个房子用绿色和刷到上一个房子用蓝色的较小值，
			这样当我们算到最后一个房子时，我们只要取出三个累计花费的最小值即可。
			
   @Type: 动态规划
 * @Date 2017-09-18 11：02
 */
public class _256_Paint_House {
	
	public int minCost(int[][] costs) {
		/*
		 * 假设：当前房为i,当前房用红色刷,红色为0			//总共3种颜色 0:红, 1:蓝, 2:绿 
		 * 那么：
		 * 		i-1:前一间房子只能用蓝色或绿色 即：(j+1)%3或(j+2)%3
		 * 				刷到上一间房的最小成本就为 刷上一间房用蓝色或绿色的最小值 
		 * 					即:min(cost[i-1][(j+1)%3], cost[i-1][(j+2)%3]
		 * 		要刷到当前这间为i的房子,(总)成本就为：
		 * 			当前这间房的成本加上刷上间房的最小成本
		 * 			 		即:dp[i][j]+min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]
		 */
		if (costs==null || costs.length==0)	return 0;
		for (int i = 1; i < costs.length; i ++) {
			//刷红色的情况
			costs[i][0] = costs[i][0] + Math.min(costs[i-1][1], costs[i-1][2]);
			//刷蓝色的情况
			costs[i][1] = costs[i][1] + Math.min(costs[i-1][0], costs[i-1][2]);
			//刷绿色的情况
			costs[i][2] = costs[i][2] + Math.min(costs[i-1][0], costs[i-1][1]);
		}
		TraverseUtils.println("画房子", costs);
		//求出所有情况后,找出其中成本最低的
		return findMinCost(costs);
		
	}
	
	/**
	 * 
	 * @param costs
	 * @return
	 */
	private int findMinCost(int[][] costs) {
		int N = costs.length;
		int cost1 = costs[N-1][0], cost2 = costs[N-1][1], cost3 = costs[N-1][1];
		return Math.min(Math.min(cost1, cost2), cost3);			//找出3个结果中的最小值
	}	
	public void traverse(int[] nums) {
		for (int i : nums) {
			LogUtils.print(i);
		}
	}
    
	public static void main(String[] args) {
		_256_Paint_House obj = new _256_Paint_House();

		LogUtils.println("刷房子", obj.minCost(new int[][]			
				{
					{5, 2, 0}, 			//刷第一间房用 红色需成本5,用蓝色需成本2,用绿色需成本0	
					{2, 2, 0}
				
				}
		));								//输出结果3:
	}

}
